package table;
//Description:单项链表的主函数
//链表（一个一个节点组成的  val：数据域 next：下一个节点的位置） 单项不带头 非循环 双向不带头非循环
//用head存储第一个节点（头节点）的地址  head.next存储的就是下一个节点的地址  最后一个节点（尾结点）他的next域为null
//链表在堆上
public class Main {
    //合并两个有序链表
    public ListNode merge(ListNode head1,ListNode head2){
        ListNode newHead = new ListNode(-1);//傀儡节点
        ListNode tmp = newHead;
        while(head1 != null && head2 != null){//任意一个为空了就结束了
            if(head1.val > head2.val){
                tmp.next = head2;//把较小的先放在傀儡节点的后面
                head2 = head2.next;//然后向后走
                tmp = tmp.next;//让新链表往后走 接收下一个节点
            }else{
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }
        }
        if(head1 != null){//如果是第二个链表先结束 就把第一个链表后面的值连接在新链表后面
            tmp.next = head1;
        }else{
            tmp.next = head2;
        }
        return newHead.next;//返回新的头节点（傀儡节点没用）
    }
    public ListNode intersect(ListNode head1,ListNode head2){
            if(head1 == null || head2 == null) return null;
            ListNode cur1 = head1;
            ListNode cur2 = head2;
            int a = 0;
            int b = 0;
            while(cur1 != null){//找长度
                a++;
                cur1 = cur1.next;
            }
            cur1 = head1;
            while(cur2 != null){
                b++;
                cur2 = cur2.next;
            }
            cur2 = head2;
            if(a > b){//走差值步 （a大就走 链表一 ，b大就走链表二）
                while(a - b != 0){
                    cur1 = cur1.next;
                }
            }else{
                while(b - a != 0){
                    cur2 = cur2.next;
                }
            }
            while(cur1 != cur2){//同时走直到相遇
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur2;
        }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(15);
        myLinkedList.addLast(12);
        myLinkedList.addFirst(11);
        myLinkedList.addIndex(3,13);
        myLinkedList.display();

        myLinkedList.display2(myLinkedList.partition(15));
        //myLinkedList.display2(myLinkedList.delete(16));
        //System.out.println(myLinkedList.size());
        //System.out.println(myLinkedList.contains(17));
        // myLinkedList.remove(17);
        //myLinkedList.display();
         //myLinkedList.removeAllKey(12);
         //myLinkedList.display();
        // myLinkedList.clear();
         //myLinkedList.display();
        //myLinkedList.display2(myLinkedList.reverseList());
        //System.out.println(myLinkedList.middleNode().val);
        //System.out.println(myLinkedList.findKthToTail(5).val);*/
    }
}